{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Cycle Length Queries in a Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: cycleLengthQueries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #查询树中环的长度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数&nbsp;<code>n</code>&nbsp;，表示你有一棵含有&nbsp;<code>2<sup>n</sup> - 1</code>&nbsp;个节点的 <strong>完全二叉树</strong>&nbsp;。根节点的编号是&nbsp;<code>1</code>&nbsp;，树中编号在<code>[1, 2<sup>n - 1</sup> - 1]</code>&nbsp;之间，编号为&nbsp;<code>val</code>&nbsp;的节点都有两个子节点，满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>左子节点的编号为&nbsp;<code>2 * val</code></li>\n",
    "\t<li>右子节点的编号为&nbsp;<code>2 * val + 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个长度为 <code>m</code>&nbsp;的查询数组 <code>queries</code>&nbsp;，它是一个二维整数数组，其中&nbsp;<code>queries[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;。对于每个查询，求出以下问题的解：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>在节点编号为&nbsp;<code>a<sub>i</sub></code> 和&nbsp;<code>b<sub>i</sub></code>&nbsp;之间添加一条边。</li>\n",
    "\t<li>求出图中环的长度。</li>\n",
    "\t<li>删除节点编号为&nbsp;<code>a<sub>i</sub></code> 和&nbsp;<code>b<sub>i</sub></code>&nbsp;之间新添加的边。</li>\n",
    "</ol>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>环</strong> 是开始和结束于同一节点的一条路径，路径中每条边都只会被访问一次。</li>\n",
    "\t<li>环的长度是环中边的数目。</li>\n",
    "\t<li>在树中添加额外的边后，两个点之间可能会有多条边。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回一个长度为 <code>m</code>&nbsp;的数组<em>&nbsp;</em><code>answer</code>&nbsp;，其中&nbsp;<code>answer[i]</code>&nbsp;是第&nbsp;<code>i</code>&nbsp;个查询的结果<i>。</i></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/10/25/bexample1.png\" style=\"width: 647px; height: 128px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 3, queries = [[5,3],[4,7],[2,3]]\n",
    "<b>输出：</b>[4,5,3]\n",
    "<b>解释：</b>上图是一棵有 2<sup>3</sup> - 1 个节点的树。红色节点表示添加额外边后形成环的节点。\n",
    "- 在节点 3 和节点 5 之间添加边后，环为 [5,2,1,3] ，所以第一个查询的结果是 4 。删掉添加的边后处理下一个查询。\n",
    "- 在节点 4 和节点 7 之间添加边后，环为 [4,2,1,3,7] ，所以第二个查询的结果是 5 。删掉添加的边后处理下一个查询。\n",
    "- 在节点 2 和节点 3 之间添加边后，环为 [2,1,3] ，所以第三个查询的结果是 3 。删掉添加的边。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/10/25/aexample2.png\" style=\"width: 146px; height: 71px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 2, queries = [[1,2]]\n",
    "<b>输出：</b>[2]\n",
    "<b>解释：</b>上图是一棵有 2<sup>2</sup> - 1 个节点的树。红色节点表示添加额外边后形成环的节点。\n",
    "- 在节点 1 和节点 2 之间添加边后，环为 [2,1] ，所以第一个查询的结果是 2 。删掉添加的边。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 30</code></li>\n",
    "\t<li><code>m == queries.length</code></li>\n",
    "\t<li><code>1 &lt;= m &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>queries[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= 2<sup>n</sup> - 1</code></li>\n",
    "\t<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [cycle-length-queries-in-a-tree](https://leetcode.cn/problems/cycle-length-queries-in-a-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [cycle-length-queries-in-a-tree](https://leetcode.cn/problems/cycle-length-queries-in-a-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[[5,3],[4,7],[2,3]]', '2\\n[[1,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            if a > b:\n",
    "                a, b = b, a\n",
    "            d = b.bit_length() - a.bit_length()\n",
    "            queries[i] = d + (a ^ (b >> d)).bit_length() * 2 + 1\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "       for i, (a, b) in enumerate(queries):\n",
    "           res = 1\n",
    "           while a != b:\n",
    "               if a > b: a //= 2\n",
    "               else: b //= 2\n",
    "               res += 1\n",
    "           queries[i] = res\n",
    "       return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            if a > b: a, b = b, a  # 保证 a <= b\n",
    "            d = b.bit_length() - a.bit_length()\n",
    "            queries[i] = d + (a ^ (b >> d)).bit_length() * 2 + 1\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            res = 1\n",
    "            while a != b:\n",
    "                if a > b: a //= 2\n",
    "                else: b //= 2\n",
    "                res += 1\n",
    "            queries[i] = res\n",
    "        return queries\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        for i in range(len(queries)):\n",
    "            node0 = queries[i][0]\n",
    "            node1 = queries[i][1]\n",
    "            if node0 < node1:\n",
    "                node0, node1 = node1, node0\n",
    "            d = node0.bit_length() - node1.bit_length()\n",
    "            queries[i] = d + 2 * ((node0 >> d) ^ node1).bit_length() + 1\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            res = 1\n",
    "            while a != b:\n",
    "                if a > b: a //= 2\n",
    "                else: b //= 2\n",
    "                res += 1\n",
    "            queries[i] = res\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            res = 1\n",
    "            while a != b:\n",
    "                if a > b: a //= 2\n",
    "                else: b //= 2\n",
    "                res += 1\n",
    "            queries[i] = res\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            res = 1\n",
    "            while a != b:\n",
    "                if a > b: a //= 2\n",
    "                else: b //= 2\n",
    "                res += 1\n",
    "            queries[i] = res\n",
    "        return queries\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            res = 1\n",
    "            while a != b:\n",
    "                if a > b:\n",
    "                    a //= 2\n",
    "                else:\n",
    "                    b //= 2\n",
    "                res += 1\n",
    "            queries[i] = res\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            res = 1\n",
    "            while a != b:\n",
    "                if a > b: a //= 2\n",
    "                else: b //= 2\n",
    "                res += 1\n",
    "            queries[i] = res\n",
    "        return queries\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            res = 1\n",
    "            while a != b:\n",
    "                if a > b:\n",
    "                    a >>= 1\n",
    "                else:\n",
    "                    b >>= 1\n",
    "                res += 1\n",
    "            queries[i] = res\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            res = 1\n",
    "            while a != b:\n",
    "                if a > b: a //= 2\n",
    "                else: b //= 2\n",
    "                res += 1\n",
    "            queries[i] = res\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            if a < b:\n",
    "                a, b = b, a\n",
    "            d = a.bit_length() - b.bit_length()\n",
    "            L = (b ^ (a >> d)).bit_length()\n",
    "            # print(d, L)\n",
    "            queries[i] = d + 2 * L + 1\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            res = 1\n",
    "            while a != b:\n",
    "                if a > b: a //= 2\n",
    "                else: b //= 2\n",
    "                res += 1\n",
    "            queries[i] = res\n",
    "        return queries\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            res = 1\n",
    "            while a != b:\n",
    "                if a > b: a //= 2\n",
    "                else: b //= 2\n",
    "                res += 1\n",
    "            queries[i] = res\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            if a > b: a, b = b, a  # 保证 a <= b\n",
    "            d = b.bit_length() - a.bit_length()\n",
    "            queries[i] = d + (a ^ (b >> d)).bit_length() * 2 + 1\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            if a > b: a, b = b, a  # 保证 a <= b\n",
    "            d = b.bit_length() - a.bit_length()\n",
    "            queries[i] = d + (a ^ (b >> d)).bit_length() * 2 + 1\n",
    "        return queries\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        for i in range(len(queries)):\n",
    "            x, y = bin(queries[i][0])[2:], bin(queries[i][1])[2:]\n",
    "            j = 1\n",
    "            while j < len(x) and j < len(y) and x[j] == y[j]:\n",
    "                j += 1\n",
    "            queries[i] = len(x) + len(y) - j * 2 + 1\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        for i in range(len(queries)):\n",
    "            x, y = bin(queries[i][0])[2:], bin(queries[i][1])[2:]\n",
    "            j = 1\n",
    "            while j < len(x) and j < len(y) and x[j] == y[j]:\n",
    "                j += 1\n",
    "            queries[i] = len(x) + len(y) - j * 2 + 1\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            res = 1\n",
    "            while a != b:\n",
    "                if a > b:\n",
    "                    a //= 2\n",
    "                else:\n",
    "                    b //= 2\n",
    "                res += 1\n",
    "            queries[i] = res\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            if a > b: a, b = b, a  # 保证 a <= b\n",
    "            d = b.bit_length() - a.bit_length()\n",
    "            queries[i] = d + (a ^ (b >> d)).bit_length() * 2 + 1\n",
    "        return queries\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "对于每次查询，都需要找到一个lca\n",
    "然后计算这两点到lca的距离即可，可以边找边计算\n",
    "怎么方便的找呢？比大小\n",
    "\n",
    "找lca时每次只跳一步太慢了，注意到这是一颗完全二叉树，研究节点的二进制编号可以O(1)找到lca\n",
    "'''\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        for i,(x,y) in enumerate(queries):\n",
    "            res=1\n",
    "            while x!=y:\n",
    "                if x>y:x//=2\n",
    "                else:y//=2\n",
    "                res+=1\n",
    "            queries[i]=res  \n",
    "        return queries\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        res=[]\n",
    "        for l,r in queries:\n",
    "            c=1\n",
    "            while l!=r:\n",
    "                l,r=max(l,r), min(l,r)\n",
    "                l>>=1\n",
    "                c+=1\n",
    "            res.append(c)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        for u, v in queries:\n",
    "            if u > v:\n",
    "                u, v = v, u\n",
    "            depth_u, depth_v = u.bit_length(), v.bit_length()\n",
    "            v //= (2 ** (depth_v - depth_u))\n",
    "            upstair = 0\n",
    "            while u != v:\n",
    "                u, v = u // 2, v // 2\n",
    "                upstair += 1\n",
    "            cur = upstair * 2 + 1 + depth_v - depth_u\n",
    "            ans.append(cur)\n",
    "        return ans    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "       res = []\n",
    "       for a, b in queries:\n",
    "          s = 1\n",
    "          while a != b:\n",
    "             if a < b:\n",
    "                tmp = a\n",
    "                a = b\n",
    "                b = tmp\n",
    "             a >>= 1\n",
    "             s += 1\n",
    "          res.append(s)\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        n = len(queries)\n",
    "        ret = [0] * len(queries)\n",
    "        for i in range(n):\n",
    "            a, b = queries[i]\n",
    "            ret[i] = len(bin(a)[2:]) + len(bin(b)[2:])\n",
    "            tmp = a\n",
    "            s = set()\n",
    "            while tmp:\n",
    "                s.add(tmp)\n",
    "                tmp >>= 1\n",
    "            tmp = b\n",
    "            while tmp:\n",
    "                if tmp in s:\n",
    "                    ret[i] -= len(bin(tmp)[2:]) * 2 - 1\n",
    "                    break\n",
    "                tmp >>= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\r\n",
    "def dfs(x) -> int:\r\n",
    "    if x == 1:\r\n",
    "        return 0\r\n",
    "    return dfs(x //  2) + 1\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\r\n",
    "        res = []\r\n",
    "        def getp(x: int) -> List[int]:\r\n",
    "            rx = []\r\n",
    "            while x:\r\n",
    "                rx.append(x)\r\n",
    "                x //= 2 \r\n",
    "            return rx \r\n",
    "\r\n",
    "        for x, y in queries:\r\n",
    "            rx = getp(x)\r\n",
    "            ry = getp(y)\r\n",
    "            while rx and ry and rx[-1] == ry[-1]:\r\n",
    "                rx.pop()\r\n",
    "                ry.pop()\r\n",
    "            res.append(len(rx) + len(ry) + 1)\r\n",
    "            \r\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        m = len(queries)\n",
    "        answer = [0] * m\n",
    "        for i in range(m):\n",
    "            a, b = queries[i]\n",
    "            dis = 0\n",
    "            while a != b:\n",
    "                if a > b:\n",
    "                    a //= 2\n",
    "                else:\n",
    "                    b //= 2\n",
    "                dis += 1\n",
    "            answer[i] = dis + 1\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans=[]\n",
    "\n",
    "        for q1,q2 in queries:\n",
    "            has={}\n",
    "            d=0\n",
    "            while q1:\n",
    "                has[q1]=d  \n",
    "                d+=1\n",
    "                q1=q1//2 \n",
    "            d=0 \n",
    "            while q2:  \n",
    "                if q2 in has:    \n",
    "                    break\n",
    "                d+=1 \n",
    "                q2=q2//2\n",
    "           # print(q1,q2,has[q2],d)\n",
    "            ans.append(has[q2]+d+1) \n",
    "                \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        def lca(a, b):\n",
    "            d = dict()\n",
    "            i = 0\n",
    "            while a:\n",
    "                d[a] = i\n",
    "                i += 1\n",
    "                a = a >> 1\n",
    "            i = 0\n",
    "            while b:\n",
    "                if b in d:\n",
    "                    return i + d[b]\n",
    "                b = b >> 1\n",
    "                i += 1\n",
    "\n",
    "        return [lca(a, b) + 1 for a, b in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(queries)):\n",
    "            a,b = queries[i]\n",
    "            cnt = 0\n",
    "            while a != b:\n",
    "                if a > b:\n",
    "                    a //= 2\n",
    "                else:\n",
    "                    b //= 2\n",
    "                cnt += 1\n",
    "            res.append(cnt+1) \n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        for a, b in queries:\n",
    "            ans = 1\n",
    "            while a != b:\n",
    "                if a > b:\n",
    "                    a //= 2 \n",
    "                else:\n",
    "                    b //= 2 \n",
    "                ans += 1 \n",
    "            res.append(ans)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def both_father(self,a1,a2):\n",
    "        father_a = {}\n",
    "        k = max(a1,a2)\n",
    "        j = min(a1,a2)\n",
    "        a1 = 0\n",
    "        a2 = 0\n",
    "        while(k != j and k>0 and j>0):\n",
    "            if k>j:\n",
    "                k = int(k/2)\n",
    "                a1 +=1\n",
    "            else:\n",
    "                j = int(j/2)\n",
    "                a2 +=1\n",
    "        return a1,a2\n",
    "            \n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        answer = []\n",
    "        for nums in queries:\n",
    "            a1,a2 = self.both_father(nums[0],nums[1])\n",
    "            answer.append(a1+a2+1)\n",
    "                # answer.append(int(math.log(nums[0],2)-both_f)+int(math.log(nums[1],2)-both_f)+1)\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            s = 0\n",
    "            while a != b:\n",
    "                if a > b:\n",
    "                    a //= 2\n",
    "                else:\n",
    "                    b //= 2\n",
    "                s += 1\n",
    "            ans.append(s + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        res = [0]*len(queries)\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            a, b = bin(a), bin(b)\n",
    "            nab = min(len(a), len(b))\n",
    "            j = 3\n",
    "            while j < nab and a[j] == b[j]:\n",
    "                j += 1\n",
    "            res[i] = len(a) + len(b) - j*2 + 1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        res=[]\n",
    "        for x,y in queries:\n",
    "            s1=[]\n",
    "            s2=[]\n",
    "            while(x!=0 or y!=0):\n",
    "                if(x>0):\n",
    "                    s1.append(x)\n",
    "                if(y>0):\n",
    "                    s2.append(y)\n",
    "                x=x//2\n",
    "                y=y//2\n",
    "            i=len(s1)-1\n",
    "            j=len(s2)-1\n",
    "            while(i>=0 and j>=0 and s1[i]==s2[j]):\n",
    "                i-=1\n",
    "                j-=1\n",
    "            res.append(i+j+3)     \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            if a > b: a, b = b, a\n",
    "            d = b.bit_length() - a.bit_length()\n",
    "            ans.append(d + (a ^ (b >> d)).bit_length() * 2 + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        def qurey(k):\n",
    "            if k % 2 == 0:\n",
    "                return k //2\n",
    "            else:\n",
    "                return (k-1) //2\n",
    "            \n",
    "\n",
    "        li = []\n",
    "        for i,j in queries:\n",
    "            n1,n2 = i,j\n",
    "            ans = 0\n",
    "            while n1 != n2:\n",
    "                n1,n2 = max(n1,n2),min(n1,n2)\n",
    "                if n1!= 1:\n",
    "                    n1 = qurey(n1)\n",
    "                    ans+=1\n",
    "            li.append(ans+1)\n",
    "\n",
    "        return li"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        for a, b in queries:\n",
    "            ans = 1\n",
    "            while a != b:\n",
    "                if a > b:\n",
    "                    a //= 2 \n",
    "                else:\n",
    "                    b //= 2 \n",
    "                ans += 1 \n",
    "            res.append(ans)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            da = db = 0\n",
    "            while a != b:\n",
    "                if a > b:\n",
    "                    a //= 2\n",
    "                    da += 1\n",
    "                else:\n",
    "                    b //= 2\n",
    "                    db += 1\n",
    "            ans.append(da + db + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        def lca(a, b):\n",
    "            d = dict()\n",
    "            i = 0\n",
    "            while a:\n",
    "                d[a] = i\n",
    "                i += 1\n",
    "                a = a >> 1\n",
    "            i = 0\n",
    "            while b:\n",
    "                if b in d:\n",
    "                    # print(d[b], i)\n",
    "                    return i + d[b]\n",
    "                b = b >> 1\n",
    "                i += 1\n",
    "\n",
    "        return [lca(a, b) + 1 for a, b in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = [0 for i in range(len(queries))]\n",
    "        for i in range(len(queries)):\n",
    "            node0 = queries[i][0]\n",
    "            node1 = queries[i][1]\n",
    "            res = 0\n",
    "            while node0 != node1:\n",
    "                if node0 > node1:\n",
    "                    node0 //= 2\n",
    "                else:\n",
    "                    node1 //= 2\n",
    "                res += 1\n",
    "            ans[i] = res + 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def both_father(self,a1,a2):\n",
    "        father_a = {}\n",
    "        k = max(a1,a2)\n",
    "        j = min(a1,a2)\n",
    "        a1 = 0\n",
    "        a2 = 0\n",
    "        while(k != j and k>0 and j>0):\n",
    "            if k>j:\n",
    "                k = int(k/2)\n",
    "                a1 +=1\n",
    "            else:\n",
    "                j = int(j/2)\n",
    "                a2 +=1\n",
    "        return a1,a2\n",
    "            \n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        answer = []\n",
    "        for nums in queries:\n",
    "            a1,a2 = self.both_father(nums[0],nums[1])\n",
    "            answer.append(a1+a2+1)\n",
    "                # answer.append(int(math.log(nums[0],2)-both_f)+int(math.log(nums[1],2)-both_f)+1)\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        res=[]\n",
    "        for x,y in queries:\n",
    "            if(x>y):\n",
    "                t=x\n",
    "                x=y\n",
    "                y=t\n",
    "            a=0\n",
    "            b=0\n",
    "            while(1):\n",
    "                while(x<y):\n",
    "                  y=y//2\n",
    "                  b+=1\n",
    "                if(x==y):\n",
    "                    break\n",
    "                x=x//2\n",
    "                a+=1\n",
    "            res.append(a+b+1)     \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = [0 for i in range(len(queries))]\n",
    "        for i in range(len(queries)):\n",
    "            node0 = queries[i][0]\n",
    "            node1 = queries[i][1]\n",
    "            if node0 < node1:\n",
    "                node0, node1 = node1, node0\n",
    "            d = node0.bit_length() - node1.bit_length()\n",
    "            ans[i] = d + 2 * ((node0 >> d) ^ node1).bit_length() + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            res = 0\n",
    "            while a != b:\n",
    "                if a > b:\n",
    "                    a //= 2\n",
    "                    res += 1\n",
    "                elif a < b:\n",
    "                    b //= 2\n",
    "                    res += 1\n",
    "            ans.append(res + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        def process(a: int, b: int) -> int:\n",
    "            if a > b:\n",
    "                return process(b, a)\n",
    "            diff = b.bit_length() - a.bit_length()\n",
    "            return (a^(b>>diff)).bit_length()*2+diff+1\n",
    "        return [process(a,b) for a,b in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        def process(a: int, b: int) -> int:\n",
    "            if a > b:\n",
    "                return process(b, a)\n",
    "            i = a\n",
    "            path_a = [i]\n",
    "            while i != 1:\n",
    "                i //= 2\n",
    "                path_a.append(i)\n",
    "            #print(path_a)\n",
    "            j = b\n",
    "            cnt_b = 0\n",
    "            while j != 1 and (j not in path_a):\n",
    "                #print(j)\n",
    "                j //= 2\n",
    "                cnt_b += 1\n",
    "\n",
    "            cnt_a = len(path_a) if j not in path_a else path_a.index(j)+1\n",
    "            return cnt_a+cnt_b\n",
    "        \n",
    "        return [process(a,b) for a,b in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            if a > b:\n",
    "                a, b = b, a\n",
    "            d = b.bit_length() - a.bit_length()\n",
    "            res = d + (a ^ (b >> d)).bit_length() * 2 + 1\n",
    "            ans.append(res)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class PerfectBinaryTree:\n",
    "    \"\"\"\n",
    "    完全二叉树.\n",
    "    根节点编号为1,左子节点编号为2*val,右子节点编号为2*val+1.\n",
    "    \"\"\"\n",
    "\n",
    "    @staticmethod\n",
    "    def depth(u: int) -> int:\n",
    "        if u == 0:\n",
    "            return 0\n",
    "        return u.bit_length() - 1\n",
    "\n",
    "    @staticmethod\n",
    "    def lca(u: int, v: int) -> int:\n",
    "        if u == v:\n",
    "            return u\n",
    "        if u > v:\n",
    "            u, v = v, u\n",
    "        depth1, depth2 = PerfectBinaryTree.depth(u), PerfectBinaryTree.depth(v)\n",
    "        diff = u ^ (v >> (depth2 - depth1))\n",
    "        if diff == 0:\n",
    "            return u\n",
    "        len_ = diff.bit_length()\n",
    "        return u >> len_\n",
    "\n",
    "    @staticmethod\n",
    "    def dist(u: int, v: int) -> int:\n",
    "        return (\n",
    "            PerfectBinaryTree.depth(u)\n",
    "            + PerfectBinaryTree.depth(v)\n",
    "            - 2 * PerfectBinaryTree.depth(PerfectBinaryTree.lca(u, v))\n",
    "        )\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    # https://leetcode.cn/problems/cycle-length-queries-in-a-tree/description/\n",
    "    class Solution:\n",
    "        def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "            res = [0] * len(queries)\n",
    "            for i, (root1, root2) in enumerate(queries):\n",
    "                res[i] = PerfectBinaryTree.dist(root1, root2) + 1\n",
    "            return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        for a, b in queries:\n",
    "            p, q = self.cal(a), self.cal(b)\n",
    "            if len(p) >= len(q):\n",
    "                res.append(self.find(p, q))\n",
    "            else:\n",
    "                res.append(self.find(q, p))\n",
    "        return res\n",
    "            \n",
    "    def cal(self, a):\n",
    "        res = []\n",
    "        while a > 1:\n",
    "            res.append(a)\n",
    "            a //= 2\n",
    "        res.append(1)\n",
    "        return res\n",
    "\n",
    "    def find(self, p, q):\n",
    "        qs = set(q)\n",
    "        for u in p:\n",
    "            if u in qs:\n",
    "                return p.index(u) + q.index(u) + 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = [0 for i in range(len(queries))]\n",
    "        for i in range(len(queries)):\n",
    "            node0 = queries[i][0]\n",
    "            node1 = queries[i][1]\n",
    "            node0_path = []\n",
    "            node1_path = []\n",
    "            while node0 != 0:\n",
    "                node0_path.append(node0)\n",
    "                node0 //= 2\n",
    "            while node1 != 0:\n",
    "                node1_path.append(node1)\n",
    "                node1 //= 2\n",
    "            p0 = len(node0_path) - 1\n",
    "            p1 = len(node1_path) - 1\n",
    "            while node0_path[p0] == node1_path[p1]:\n",
    "                p0 -= 1\n",
    "                p1 -= 1\n",
    "            ans[i] = p0 + p1 + 3\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        def find_path(val):\n",
    "            path = []\n",
    "            while val > 0:\n",
    "                path.append(val)\n",
    "                val = val // 2\n",
    "            return path[::-1]  # reverse the path for easier LCA finding\n",
    "        \n",
    "        answer = []\n",
    "        \n",
    "        for a, b in queries:\n",
    "            path_a = find_path(a)\n",
    "            path_b = find_path(b)\n",
    "            \n",
    "            # Find the length of the prefix common to both paths\n",
    "            i = 0\n",
    "            while i < len(path_a) and i < len(path_b) and path_a[i] == path_b[i]:\n",
    "                i += 1\n",
    "            \n",
    "            # The length of the cycle would be (len(path_a) - i) + (len(path_b) - i) + 1\n",
    "            cycle_length = (len(path_a) - i) + (len(path_b) - i) + 1\n",
    "            answer.append(cycle_length)\n",
    "        \n",
    "        return answer\n",
    "\n",
    "# Test\n",
    "n = 3\n",
    "queries = [[2, 7], [1, 6], [2, 6]]\n",
    "sol = Solution()\n",
    "print(sol.cycleLengthQueries(n, queries))  # Output should be [4, 3, 3]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            cnt = 0\n",
    "            while a != b:\n",
    "                if a > b:\n",
    "                    a, b = b, a\n",
    "                if a // 2 != b // 2:\n",
    "                    cnt += 1\n",
    "                    b //= 2\n",
    "                else:\n",
    "                    a //= 2\n",
    "                    b //= 2\n",
    "                    cnt += 2\n",
    "            ans.append(cnt + 1)\n",
    "        return ans            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def both_father(self,a1,a2):\n",
    "        father_a = []\n",
    "        k = max(a1,a2)\n",
    "        j = min(a1,a2)\n",
    "        while(k>1):\n",
    "            father_a.append(k)\n",
    "            if j in father_a or j==k:\n",
    "                return j\n",
    "            else:\n",
    "                if k>j:\n",
    "                    k = int(k/2)\n",
    "                else:\n",
    "                    j = int(j/2)\n",
    "        return 1\n",
    "            \n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        answer = []\n",
    "        for nums in queries:\n",
    "            both_f = self.both_father(nums[0],nums[1])\n",
    "            if both_f>0:\n",
    "                both_f = int(log(both_f,2))\n",
    "            if int(nums[0]/2) == nums[1] or int(nums[1]/2)== nums[0]:\n",
    "                answer.append(2)\n",
    "            else:\n",
    "                answer.append(int(math.log(nums[0],2)-both_f)+int(math.log(nums[1],2)-both_f)+1)\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            \n",
    "            bit_a = a.bit_length()\n",
    "            bit_b = b.bit_length()\n",
    "            \n",
    "            res = 1\n",
    "            while bit_a > bit_b:\n",
    "                a //= 2\n",
    "                bit_a -= 1\n",
    "                res += 1\n",
    "            \n",
    "            while bit_b > bit_a:\n",
    "                b //= 2\n",
    "                bit_b -= 1\n",
    "                res += 1\n",
    "            \n",
    "            while a != b:\n",
    "                a //= 2\n",
    "                b //= 2\n",
    "                res += 2\n",
    "            ans.append(res)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            q_a = deque()\n",
    "            while a:\n",
    "                q_a.appendleft(a)\n",
    "                a //= 2\n",
    "            q_b = deque()\n",
    "            while b:\n",
    "                q_b.appendleft(b)\n",
    "                b //= 2\n",
    "            i = 0\n",
    "            while i < min(len(q_a), len(q_b)) and q_a[i] == q_b[i]:\n",
    "                i += 1\n",
    "            i -= 1\n",
    "            ans.append(len(q_a) + len(q_b) - 2 * i - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        '''\n",
    "           0\n",
    "         1   2\n",
    "        3 4 5 6\n",
    "        '''\n",
    "        \n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            a2 = a\n",
    "            b2 = b\n",
    "            vis = set()\n",
    "            while a2 != 0:\n",
    "                vis.add(a2)\n",
    "                a2 //= 2\n",
    "            \n",
    "            lca = 1\n",
    "            while b2 != 0:\n",
    "                if b2 not in vis:\n",
    "                    b2 = b2 // 2\n",
    "                else:\n",
    "                    lca = b2\n",
    "                    break\n",
    "            res = 1\n",
    "            while a != lca:\n",
    "                res += 1\n",
    "                a //= 2\n",
    "            while b != lca:\n",
    "                res += 1\n",
    "                b //= 2\n",
    "            ans.append(res)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        for s, e in queries:\n",
    "            l, cnt = [], 1\n",
    "            while s!=0: \n",
    "                l.append(s)\n",
    "                s //= 2\n",
    "            while e not in l:\n",
    "                cnt += 1\n",
    "                e //= 2\n",
    "            res.append(l.index(e)+cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        def getDepth(root: int) -> int:\n",
    "            return root.bit_length() - 1\n",
    "\n",
    "        def getLCA(a: int, b: int) -> int:\n",
    "            \"\"\"\n",
    "            https://leetcode.cn/problems/cycle-length-queries-in-a-tree/solutions/1/shinei-by-vclip-ch6n/\n",
    "            1. 一个结点从最高位的 1开始,往下遍历每一个二进制位,得到的就是从根节点出发走到这个结点的路径选择,\n",
    "               0代表向左,1代表向右;\n",
    "            2. 求出两个结点的深度，然后把较深结点向上移动，对齐到另一个节点，让两者的二进制位对应上;\n",
    "            3. 之后，对两个二进制数求异或，异或值就代表了两者选择路径时走的方向不同的位置，\n",
    "               异或为0,说明a就是LCA;否则上跳\n",
    "            \"\"\"\n",
    "            if a == b:\n",
    "                return a\n",
    "            if a > b:\n",
    "                a, b = b, a\n",
    "            depthA, depthB = a.bit_length() - 1, b.bit_length() - 1\n",
    "            diff = a ^ (b >> (depthB - depthA))\n",
    "            if diff == 0:\n",
    "                return a\n",
    "            len_ = diff.bit_length()\n",
    "            return a >> len_\n",
    "\n",
    "        res = [0] * len(queries)\n",
    "        for i, (root1, root2) in enumerate(queries):\n",
    "            lca = getLCA(root1, root2)\n",
    "            res[i] = getDepth(root1) + getDepth(root2) - 2 * getDepth(lca) + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        for a, b in queries:\n",
    "            tmp = 1\n",
    "            while a!=b:\n",
    "                if a>b:\n",
    "                    a //= 2\n",
    "                else:\n",
    "                    b //= 2\n",
    "                tmp+=1\n",
    "            res.append(tmp)\n",
    "        \n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
